SWERC 2013 D Decoding the Hallway

发表于 | 更新于 | 分类于 ， ， | 阅读次数：
本文字数： 1.6k | 阅读时长 ≈ 1 分钟

task

爱德华为了恢复国家炼金术师的称号而再次参加试炼，只是今年的试炼内容有点坑。
炼金术师们将面对一道长长的直走廊，然后从左边进入，右边出来，这样走n次。每一次，炼金术师们遇到一条直的走廊就按先右后左的顺序将其弯曲，例如：
Alt text

图1，原先是一条直的走廊(虚线)，现在炼金术师将其弯折向右(实线)。
图2，现在走廊由两段直线构成(虚线)，现在炼金术师先将第一段弯折向右，然后第二段向左弯折(实线)。
图3，现在现在走廊由四段直线构成(虚线)，现在炼金术师依次按右左右左的顺序弯折4条线段(实线)。
在接下去就变成了图4和图5所示。
钢之炼金术师爱德华是非常厉害的，所以他非常完美地完成了试炼。现在轮到裁判们去判断他是否做的正确了。裁判将从左进入走廊，然后从右走出走廊。途中，他会记录自己每次转弯的方向，如果向右转，那么就是R，如果向左转就是L。所以当n=1时，该裁判将会记下L。当n=2，该裁判会记下LLR。当n=4是那么裁判写下的就是LLRLLRRLLLRRLRR了。
显然字符串的长度会随n的增长而呈指数级增长。他将很难判断这个字符串是否正确。所以现在他会给出一个字符串，只要判断这个字符串是否在原串中即可。
n<=1000,s的长度<=100

solution

我们把n=1,2,3,4,5时的字符串列出来后，我们可以发现相邻两个字符串之间的联系。

n string
1 L
2 LLR
3 LLRLLRR
4 LLRLLRRLRRLRRLL
5 LLRLLRRLRRLRRLLLRRLRRLLRLLRLLRR

显然对于第i个字符串，就是第i-1个字符串加一个‘L’和将第i-1个字符串中的每个字符取反之后的字符串(L->R,R->L)。
虽然字符串是随n变大而指数级增长，但是给出的子串的长度只有100.那么是否只要n到达某一值，它就包括了之后所有的字符串中小于等于100分子串？
事实证明是的，这个n就等于10。
所以我们就可以预处理出n=1,2,3,4,5,6,7,8,9,10时的字符串，然后n小于10的情况我们就可以直接判断，而n>=10的情况我们都在n==10的字符串中判断。
至于为什么n等于10，根据每个字符串与上一个串的关系，如果我们将第一个超过100的串设为LLR(即n=7)，接下来的字符串中任意一个长度为100的子串的跨度都不会超过3个字符，那么我们根据上述的表我们可以等出当n==6是，就会出现所有的字符长度为3的字符串，同理可得当n=7+6-2-1=10是就可以出现所有n==100的字符

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
#include <iostream>
#include <cstdio>
#include <string>
#include <algorithm>
using namespace std;
char str[105];
string res[11];
int m;
void Init(){
	res[0]="L";
	while(++m<9){
		int len=res[m-1].size();
		for(int i=0;i<len;i++)res[m]+=(i&1?'R':'L'),res[m]+=res[m-1][i];
		res[m]+='R';
	}
}
int main(){
	int T,n,o=0;
	Init();
	scanf("%d",&T);
	while(T--&&scanf("%d %s",&n,str)){
		if(~res[min(n,m)-1].find(str))printf("Case %d: Yes\n",++o);
		else printf("Case %d: No\n",++o);
	}
	return 0;
}